package cn.com.yang.egg;

import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

public class Topic0001 {

	/**
	 * n 为 乘客的数量
	 * 
	 * @param n
	 */
	public double test1(int n) {
		if (n == 1) {
			return 1.0000;
		} else if (n >= 2) {
			return 0.5;
		} else {
			return 0.00;
		}
	}

	/**
	 * 太慢了
	 * @param nums
	 * @param target
	 * @return
	 */
	public static int[] twoSum(int[] nums, int target) {
		int[] arr = new int[2];
		for (int i = 0; i < nums.length; i++) {
			for (int j = i + 1; j < nums.length; j++) {
				if (nums[i] + nums[j] == target) {
					arr[0] = i;
					arr[1] = j;
					break;
				}
			}
		}
		return arr;
	}
	/**
	 * 好啊
	 * @param nums
	 * @param target
	 * @return
	 */
	public static int[] twoSum2(int[] nums, int target) {
		int[] arr = new int[2];
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		for(int i=0;i<nums.length;i++) {
			int temp = target-nums[i];
			if (map.containsKey(temp)) {
				arr[0]=i;
				arr[1]=map.get(temp);
			}
			map.put(nums[i], i);
		}
		
		return arr;
	}

	/**
	 * 太慢了
	 * @param height
	 * @return
	 */
	public int maxArea(int[] height) {
        //1.计算所有的面积，用一个容器撑起来  
        Set<Integer> hash = new HashSet();
		//TreeSet<Integer> set = new TreeSet<>(((o1,o2)->o1.compareTo(o2)));
        for(int i= 0;i<height.length;i++ ){
            for (int j=i+1;j<height.length;j++ ){
                if(height[i]>height[j]){
                    hash.add(height[j]*(j-i));
                }else{
                    hash.add(height[i]*(j-i));
                }
            }
        }
        return Collections.max(hash);
    }
	/**
	 * 换个算法，计算 柱状图面积
	 * @param height
	 * @return
	 */
	public static int maxArea2(int[] height) {
		int size  = height.length;
		int left = 0,right = size-1;
		int max=0;
		while(left < right) {
			max = Math.max(max,(right-left)*(Math.min(height[left],height[right])));
			if (height[left]>height[right]) {
				--right;
			}else {
				++ left;
			}
		}
        return max;
    }
	/**
	 * 斐波那契数
	 * @param n
	 * @return
	 */
	public int fib(int n) {
        if (n <= 1) return n;
        int first = 0;
        int second = 1;
        int result = 0;
        while (--n > 0) {
            result = first + second;
            if (result >= 1000000007) {
                result -= 1000000007;
            }
            first = second;
            second = result;
        }
        return result;
    }
	public static void main(String[] args) {
		maxArea2(new int[] {123,434,545,651,223,11});
//		System.out.println(twoSum(new int[] { 2, 7, 11, 15 }, 9).toString());
//		System.out.println(twoSum2(new int[] { 2, 7, 11, 15 }, 9).toString());
		
	}
}
